class Solution(object):
    def numTilings(self, n):
        """
        :type n: int
        :rtype: int
        """
        last1 = [0, 0]
        last2 = [0, 0]
        base = 10 ** 9 + 7
        for i in range(n):
            if i == 0:
                last1[i] = 1
            if i == 1:
                last1[i] = 2
                last2[i] = 2
            if i >= 2:
                last2[i % 2] = (2 * last1[i % 2] + last2[(i + 1) % 2]) % base
                last1[i % 2] = (last1[(i + 1) % 2] + last1[i % 2] + last2[(i + 1) % 2]) % base
        return last1[(n - 1) % 2]


data = Solution()
n = 3
print(data.numTilings(n))
